package com.lzq.leetcode;


import java.awt.List;
import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;

public class TestAPI {

    static int INF = Integer.MAX_VALUE;
    static int mod = 1000000007 ;
    static int N = 1001000,M = 2*N;
    static int[] dp = new int[N],st = new int[N];
    static int n,m;
    static long ans;
    //递推思想，如果x删了一个数位后的那个数，能通过若干次删除得到一个质数，那么x就是一个质数

    //去除idx位置的值后的新数
    static int solve(char[] s,int idx){
        int res = 0;
        for(int i=0;i<s.length;i++){
            if(idx!=i){
                res = res * 10 + (s[i]-'0');
            }
        }

        return res;
    }


    public static void main(String[] args) throws IOException {
        n = 1000000;
        for(int i=2;i<=n;i++){
            if(st[i]==0){
                dp[i] = 1;
                if((long) i*i > n) continue;
                for(int j=i*i;j<=n;j+=i)
                    st[j] = 1;
            }
        }
        for(int i=1;i<=n;i++){
            char[] s = Integer.toString(i).toCharArray();
            for(int j=0;j<s.length;j++){
                int val = solve(s,j);
                // System.out.println(i+" "+val);
                dp[i] |= dp[val];
            }
            if(dp[i]==1) ans += 1;
            //   System.out.println(i+" "+dp[i]);
        }
        System.out.println(ans);

    }

    static Scanner sc = new Scanner(System.in);

}
